package 二叉树高频题目_上_不含树型dp;

/**
 * @author 冷加宝
 * @version 1.0
 */
// 二叉树的最大特殊宽度
// 测试链接 : https://leetcode.cn/problems/maximum-width-of-binary-tree/
public class Code03_WidthOfBinaryTree {

    class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
    }

    // 提交以下的方法
    // 用每次处理一层的优化bfs就非常容易实现
    // 如果测试数据量变大了就修改这个值
    public static int MAXN = 3001;
    // 数组队列，存储二叉树不空的节点
    public TreeNode[] nq = new TreeNode[MAXN];
    // 与二叉树不空的队列存储节点的序号值相对应，设根节点的序号值为1
    public int[] iq = new int[MAXN];
    public int l, r;

    public int widthOfBinaryTree(TreeNode root) {
        int ans = 1;
        l = r = 0;
        nq[r] = root;
        iq[r++] = 1;
        if(root != null){
            while(l < r){
                // 每一层的不空节点的个数
                int size = r - l;
                // l   ...   r-1
                ans = Math.max(ans, iq[r-1] - iq[l] + 1);
                for(int i = 0; i < size; i++){
                    TreeNode treeNode = nq[l];
                    int index = iq[l++];
                    if(treeNode.left != null){
                        nq[r] = treeNode.left;
                        iq[r++] = index * 2;
                    }
                    if(treeNode.right != null){
                        nq[r] = treeNode.right;
                        iq[r++] = index * 2 + 1;
                    }
                }
            }
        }
        return ans;
    }
}
